package own.stu.jobgib.playown.alg.solution.dp;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 坐标型动态规划
 *
 * <li>最简单的动态规划类型</li>
 * <li>给定一个序列或网格</li>
 * <li>需要找到序列中某个/些子序列或网格中的某条路径</li>
 * - 某种性质最大/最小
 * - 计数
 * - 存在性
 * <li>动态规划方程mi中的下标i表示以a;为结尾的满足条件的子序列的性质，fminl中的下标i，i表示以格子(i,i)为结尾的满足条件的路径的性质<li/>
 * - 最大值/最小值
 * - 个数
 * - 是否存在
 * <li>坐标型动态规划的初始条件fO]就是指以a,为结尾的子序列的性质</li>
 */
public class CoordinateType {

    public static void main(String[] args) {
        CoordinateType c = new CoordinateType();

        /*System.out.println(c.uniquePathsWithObstacles(new int[][]{
                {0, 0, 0},
                {0, 1, 0},
                {0, 0, 0},
        }));*/

        /*System.out.println(c.maxKilledEnemies(new char[][]{
                "0E00".toCharArray(),
                "E0WE".toCharArray(),
                "0E00".toCharArray(),
        }));*/

        System.out.println(c.canCross(new int[]{0, 1, 3, 5, 6, 8, 12, 17}));
    }

    /**
     * 63. 不同路径 II
     * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
     * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
     * 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
     * <p>
     * 网格中的障碍物和空位置分别用 1 和 0 来表示。
     * <p>
     * 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
     * 输出：2
     * 解释：3x3 网格的正中间有一个障碍物。
     * 从左上角到右下角一共有 2 条不同的路径：
     * 1. 向右 -> 向右 -> 向下 -> 向下
     * 2. 向下 -> 向下 -> 向右 -> 向右
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        /*
        还是I得思路，从上边来或者从左边来，两者和相加
         */
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;
        int[][] dp = new int[row][col];
        boolean hasObstacle = false;
        for (int i = 0; i < col; i++) {
            if (hasObstacle || obstacleGrid[0][i] == 1) {
                hasObstacle = true;
                dp[0][i] = Integer.MAX_VALUE;
            } else {
                dp[0][i] = 1;
            }
        }
        hasObstacle = false;
        for (int i = 0; i < row; i++) {
            if (hasObstacle || obstacleGrid[i][0] == 1) {
                hasObstacle = true;
                dp[i][0] = Integer.MAX_VALUE;
            } else {
                dp[i][0] = 1;
            }
        }

        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = Integer.MAX_VALUE;
                } else {
                    if (dp[i - 1][j] != Integer.MAX_VALUE) {
                        dp[i][j] += dp[i - 1][j];
                    }
                    if (dp[i][j - 1] != Integer.MAX_VALUE) {
                        dp[i][j] += dp[i][j - 1];
                    }
                }
            }
        }
        return dp[row - 1][col - 1] == Integer.MAX_VALUE ? -1 : dp[row - 1][col - 1];
    }

    /**
     * 553 · 炸弹袭击 (lintcode)
     * 给定一个二维矩阵, 每一个格子可能是一堵墙 W,或者 一个敌人 E 或者空 0 (数字 '0'), 返回你可以用一个炸弹杀死的最大敌人数. 炸弹会杀死所有在同一行和同一列没有墙阻隔的敌人。 由于墙比较坚固，所以墙不会被摧毁.
     * 你只能在空的地方放置炸弹.
     * <p>
     * 样例
     * 输入:
     * grid =["0E00","E0WE","0E00"]
     * 输出: 3
     * 解释: 把炸弹放在 (1,1) 能杀3个敌人
     */
    public int maxKilledEnemies(char[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        // 考虑四个方向
        /*
         up 表示（i，j)为空地时，放置炸弹，向上能炸死多少敌人
         dp[i][j]
         1:(i,j)是墙，dp[i][j] = 0;
         2:(i,j)是敌人,dp[i][j] = dp[i - 1][j] + 1
         3:(i,j)是空地,dp[i][j] = dp[i - 1][j]

         //初始化
         dp[0][0] （0,0）是敌人，dp[0][0] = 1, 其他dp[0][0]= 0
         */

        int[][] up = new int[row][col];
        char c = ' ';
        // 初始化：
        for (int i = 0; i < col; i++) {
            up[0][i] = grid[0][i] == 'E' ? 1 : 0;
        }
        for (int i = 1; i < row; i++) {
            for (int j = 0; j < col; j++) {
                c = grid[i][j];
                if (c == 'W') {
                    up[i][j] = 0;
                } else if (c == '0') {
                    up[i][j] = up[i - 1][j];
                } else {
                    up[i][j] = up[i - 1][j] + 1;
                }
            }
        }

        int[][] down = new int[row][col];
        for (int i = 0; i < col; i++) {
            down[row - 1][i] = grid[row - 1][i] == 'E' ? 1 : 0;
        }
        for (int i = row - 2; i >= 0; i--) {
            for (int j = 0; j < col; j++) {
                c = grid[i][j];
                if (c == 'W') {
                    down[i][j] = 0;
                } else if (c == '0') {
                    down[i][j] = down[i + 1][j];
                } else {
                    down[i][j] = down[i + 1][j] + 1;
                }
            }
        }

        int[][] left = new int[row][col];
        // 初始化：
        for (int i = 0; i < row; i++) {
            left[i][0] = grid[i][0] == 'E' ? 1 : 0;
        }
        for (int i = 0; i < row; i++) {
            for (int j = 1; j < col; j++) {
                c = grid[i][j];
                if (c == 'W') {
                    left[i][j] = 0;
                } else if (c == '0') {
                    left[i][j] = left[i][j - 1];
                } else {
                    left[i][j] = left[i][j - 1] + 1;
                }
            }
        }

        int[][] right = new int[row][col];
        // 初始化：
        for (int i = 0; i < row; i++) {
            right[i][col - 1] = grid[i][col - 1] == 'E' ? 1 : 0;
        }
        for (int i = 0; i < row; i++) {
            for (int j = col - 2; j >= 0; j--) {
                c = grid[i][j];
                if (c == 'W') {
                    right[i][j] = 0;
                } else if (c == '0') {
                    right[i][j] = right[i][j + 1];
                } else {
                    right[i][j] = right[i][j + 1] + 1;
                }
            }
        }

        int max = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '0') {
                    max = Math.max(max, up[i][j] + down[i][j] + right[i][j] + left[i][j]);
                }
            }
        }
        return max;
    }

    /**
     * 403. 青蛙过河
     * 一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内都有可能放有一块石子（也有可能没有）。 青蛙可以跳上石子，但是不可以跳入水中。
     * 给你石子的位置列表 stones（用单元格序号 升序 表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一块石子上）。开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃 1 个单位（即只能从单元格 1 跳至单元格 2 ）。
     * 如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。
     * <p>
     * 示例：
     * 输入：stones = [0,1,3,5,6,8,12,17]
     * 输出：true
     * 解释：青蛙可以成功过河，按照如下方案跳跃：跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后，跳 5 个单位到第 8 个石子（即最后一块石子）。
     */
    public boolean canCross(int[] stones) {
        if (stones == null || stones.length == 0) {
            return false;
        }
        int n = stones.length;
        if (n == 1) return true;
        if (stones[0] != 0 || stones[1] != 1) {
            return false;
        }

        // 当前石头位置，<当一跳调到这里的用的步数 集合>
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int i = 0; i < stones.length; i++) {
            map.put(stones[i], new HashSet<>());
        }
        map.get(0).add(0);
        for (int i = 0; i < stones.length; i++) {
            int s = stones[i];
            Set<Integer> steps = map.get(s);
            for (Integer step : steps) {
                // step - 1
                Set<Integer> tmp = null;
                if (step > 1) {
                    tmp = map.get(s + step - 1);
                    if (tmp != null) {
                        tmp.add(step - 1);
                    }
                }
                // step
                tmp = map.get(s + step);
                if (tmp != null) {
                    tmp.add(step);
                }

                // step + 1
                tmp = map.get(s + step + 1);
                if (tmp != null) {
                    tmp.add(step + 1);
                }
            }
        }
        return !map.get(stones[n - 1]).isEmpty();
    }

    public boolean canCross_ii(int[] stones) {
        if (stones == null || stones.length == 0) {
            return false;
        }
        int n = stones.length;
        if (n == 1) return true;
        if (stones[0] != 0 || stones[1] != 1) {
            return false;
        }
        /*
        dp[i][j]表示最后一跳 跳j能否调到位置 i
        dp[k][j - 1] || dp[k][j] || dp[k][j + 1] (s[k] = s[i] - j)

        dp[1][1] = true, 能够从第0个位置1跳 到达位置1
         */
        boolean[][] dp = new boolean[n + 1][n + 1];
        dp[1][1] = true;
        for (int i = 2; i < n; i++) {
            for (int j = 1; j < i; j++) {
                // 我们知道从位置 j 到位置 i 是需要步长为 k 的跳跃
                int k = stones[i] - stones[j];
                // 而从位置 j 发起的跳跃最多不超过 j + 1
                // 因为每次跳跃，下标至少增加 1，而步长最多增加 1
                if (k <= j + 1) {
                    dp[i][k] = dp[j][k - 1] || dp[j][k] || dp[j][k + 1];
                }
            }
        }
        for (int i = 1; i < n; i++) {
            if (dp[n - 1][i]) return true;
        }
        return false;
    }
}
